<HEAD><TITLE>CEOI 2003 - Contest Environment</TITLE>
</HEAD>
<BODY>
<H1>The Race</H1>
<P>During the Annual Interstellar Competition for Tuned Spaceships, N spaceships 
will be competing. Each spaceship i is tuned in such a way that it can 
accelerate in zero time to its maximum speed V<SUB>i</SUB> and remain cruising 
at that speed. Due to past achievements, each spaceship starts at a starting 
position X<SUB>i</SUB>, specifying how many kilometers the spaceship is away 
from the starting line. </P>
<P>The race course is infinitely long. Because of the high speeds of the 
spaceships, the race course goes straight all the time. On that straight course, 
spaceships can pass one another very easily, without interfering with each 
other. </P>
<P>Many people in the audience have not realized yet that the outcome of the 
race can be determined in advance. It is your task to show this to them, by 
telling them how many times spaceships will pass one another, and by predicting 
the first 10&nbsp;000 times that spaceships pass in chronological order. </P>
<P>You may assume that each spaceship starts at a different position. 
Furthermore, there will never be more than two spaceships at the same position 
of the course at any time. </P>
<P align=center><IMG height=178 alt="the race example" 
src="0036.gif" width=380> </P>

<H2>Input</H2>
<P>The first line of the input file <TT>therace.in</TT> specifies the number of 
spaceships N (0 &lt; N <= 250&nbsp;000) that are competing. Each of the next N 
lines describe the properties of one spaceship. The i+1th line describes the ith 
ship with two integers X<SUB>i</SUB> and V<SUB>i</SUB>, representing the 
starting position and the velocity of the ith spaceship (0 <= X<SUB>i</SUB> <= 
1&nbsp;000&nbsp;000, 0 &lt; V<SUB>i</SUB> &lt; 100). The spaceships are ordered 
according to the starting position, i.e. X<SUB>1</SUB> &lt; X<SUB>2</SUB> &lt; 
... &lt; X<SUB>N</SUB>. The starting position is the number of kilometers past 
the starting line where the spaceship starts, and the velocity is given in 
kilometers per second. </P>

<H2>Output</H2>
<P>The first line of the output file <TT>therace.out</TT> should contain the 
number of times that spaceships pass one another during the race {\bf modulo 
1&nbsp;000&nbsp;000}. By publishing the number of passes only modulo 
1&nbsp;000&nbsp;000, you can at the same time prove your knowledge of it and 
don't spoil the party for the less intelligent people in the audience. </P>
<P>Each of the subsequent lines should represent one passing, in chronological 
order. If there would be more than 10&nbsp;000 passings, only output the first 
10&nbsp;000 passings. If there are less than 10&nbsp;000 passings, output all 
passings. Each line should consist of two integers i and j, specifying that 
spaceship i passes spaceship j. If multiple passings occur at the same time, 
they have to be sorted by their position on the course. This means that passings 
taking place closer to the starting line must be listed first. The time of a 
passing is the time when the two spaceships are at the same position. </P>

<H2>Remarks</H2>
<P>If you give the correct number of passings, you will earn 40% of the score 
per test case. For correctly giving the first 10&nbsp;000 passings, you will 
earn the remaining 60% of the score. Each part is graded separately given that 
the program terminates normally within the time limit. </P>

<H2>Sample Input</H2>
<pre>
4 
0 2
2 1
3 8
6 3
</pre>

<h2>Sample Output</h2>
<pre>
2
3 4
1 2
</pre>

<H4>Time limit:</H4>8 seconds per input file 
</BODY></HTML>
